#include<bits/stdc++.h>
using namespace std;
typedef struct Lnode{
    int data;
    struct Lnode *next;
}*ls;
typedef struct TNode{
    int val;
    struct TNode *lchild;
    struct TNode *rchild;
}*tree;
ls create_ls(ls head){//不带头结点的形式
    if(head==NULL){
        head=(ls)malloc(sizeof(struct Lnode));
        scanf("%d",&head->data);
        head->next=NULL;
    }
    int x;
    scanf("%d",&x);
    while(x!=-1){
        //头插法
        ls node=(ls)malloc(sizeof(struct Lnode));
        node->data=x;
        node->next=head;
        head=node;
        scanf("%d",&x);
    }
    return head;
}
ls create_lsHaveHead(ls head){
    if(head==NULL){
        head=(ls)malloc(sizeof(struct Lnode));
        head->next=NULL;
    }
    int x;
    scanf("%d",&x);
    while(x!=-1){
        ls node=(ls)malloc(sizeof(struct Lnode));
        node->data=x;
        node->next=head->next;
        head->next=node;
        scanf("%d",&x);
    }
    return head;
}
void printList(ls head){
    ls p=head;
    while(p){
        printf("%d->",p->data);
        p=p->next;
    }
    printf("\n");
}
void NotHeadReverse(ls &L){//不带头结点，注意这里要穿指针的引用才会随着函数体中传参的改变而改变主函数中传入的值
    ls beg=L,end=L->next;
    ls p;
    while(end){
        p=end;
        beg->next=end->next;
        end->next=L;
        L=end;
        end=beg->next;
    }
    // ls p1=L;
    // while(p1){
    //    printf("%d->",p1->data);
    //     p1=p1->next;
    // }
    // return L;//好像光改当前节点的值不会改变什么(因为L保存的始终是传进来的L的地址)，只有改next之前的L才会变
    // 不应该的啊
    /*
    1、首先申明一个变量，例如是m：int m=100。
    理解为在内存中有一个名叫m的内存，里面存着100。
    2、将b指向m：int *b=&m。
    指针b指向m，b----------------->m，则b中存放m内存的地址。
    3、int *a，将b赋值给a，a=b。
    a=b，将b中的内容给a，即是将b中m内存的地址赋值给a，a中存放的也是m的地 址，a-------------------->m。
    */
}
void HaveHeadReverse(ls head){
    ls beg=head->next,end=head->next->next;
    while(end){
        beg->next=end->next;
        end->next=head->next;
        head->next=end;
        end=beg->next;
    }
}
void HaveHeadReverse2(ls L){
    ls beg=L,end=L->next;
    L->next=NULL;
    while(end){
        beg=end->next;
		end->next=L->next;
		L->next=end;
		end=beg;
    }
}

void countS(char s[],int n){
    int b[10];
    b[0]=1;//首字符置1
    for(int i=1;i<n;i++){
        if(s[i]==s[i-1])//快下标去记录是否连续出现，如果连续，将除了第一个之外的后面的标记为0
            b[i]=0;
        else
            b[i]=1;
    }
    for(int i=0;i<n;i++){
        if(b[i]!=0){
            int sum=b[i];
            for(int j=i+1;j<n;j++){
                if(s[i]==s[j]){
                    sum+=b[j];
                    b[j]=0;//已纳入 记录总数 的后续相同的字符置0不再遍历
                }
            }
            printf("%c:%d\n",s[i],sum);
        }
    }
}
/*
给定一颗二叉树，若二叉树的某个结点，其左子树所有节点之和与右子树所有结点之和相等，
则称该节点为平衡节点，编写函数，判断节点值为整数的二叉树是否存在平衡结点。
*/
tree newNode(int val){
    tree node=(tree)malloc(sizeof(struct TNode));
    node->val=val;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}
tree create_Tree(tree root,int val){
    if(root==NULL)
        return newNode(val);
    if(root->val>val){
        root->lchild=create_Tree(root->lchild,val);
    }else{
        root->rchild=create_Tree(root->rchild,val);
    }
    return root;
}

void preOrderRecursion(tree root){
    if(root==NULL)  
        return;
    printf("%d ",root->val);
    preOrderRecursion(root->lchild);
    preOrderRecursion(root->rchild);
}
// 先序非递归
void preOrder(tree root){
    if(root==NULL)
        return;
    stack<tree> s;
    s.push(root);
    while(!s.empty()){
        tree node=s.top();
        printf("%d ",node->val);
        s.pop();
        if(node->rchild!=NULL) s.push(node->rchild);
        if(node->lchild!=NULL) s.push(node->lchild);//后入先出
    }
}

void inOrderRecursion(tree root){
    if(root==NULL)
        return;
    inOrderRecursion(root->lchild);
    printf("%d ",root->val);
    inOrderRecursion(root->rchild);
}
// 中序非递归
void inOrder(tree root){
    stack<tree> s;
    tree cur=root;
    while(cur||!s.empty()){
        while(cur){
            s.push(cur);
            cur=cur->lchild;
        }
        cur=s.top();
        printf("%d ",cur->val);
        s.pop();
        cur=cur->rchild;
    }
}

void postOrderRecursion(tree root){
    if(root==NULL)
        return;
    postOrderRecursion(root->lchild);
    postOrderRecursion(root->rchild);
    printf("%d ",root->val);
}

void postOrder(tree root){//根左右--->右左根    根右左--->左右根
    if(root==NULL)
        return;
    stack<tree> s;
    s.push(root);
    stack<tree> res;
    while(!s.empty()){
        tree node=s.top();
        res.push(node);
        s.pop();
        if(node->lchild) s.push(node->lchild);
        if(node->rchild) s.push(node->rchild);//后入先出
    }
    while(!res.empty()){
        printf("%d ",res.top()->val);
        res.pop();
    }
}
void levelOrder(tree root){
    if(root==NULL)
        return;
    queue<tree> q;
    q.push(root);
    while(!q.empty()){
        tree node=q.front();
        printf("%d ",node->val);
        q.pop();
        if(node->lchild) q.push(node->lchild);
        if(node->rchild) q.push(node->rchild);
    }
}
int main(){
    ls head=NULL;
    // 带头结点的版本
    // head=create_lsHaveHead(head);
    // printList(head->next);
    // HaveHeadReverse2(head);
    // printList(head->next);

    // 不带头结点的版本
    head=create_ls(head);
    printList(head);
    NotHeadReverse(head);
    printList(head);

    //统计字符
    // char s[6]={'a','a','c','b','c','\0'};
    // countS(s,sizeof(s)/sizeof(s[0])-1);
    /*
    tree root=NULL;
    int arr[7]={40,30,30,10,10,60,60};
	for(int i=0;i<7;i++){
		root=create_Tree(root,arr[i]);
	}
    printf("\n-----------------1.先序递归遍历-----------------\n");
    preOrderRecursion(root);
    printf("\n先序非递归遍历\n");
    preOrder(root);
    printf("\n-----------------2.中序递归遍历-----------------\n");
    inOrderRecursion(root);
    printf("\n中序非递归遍历\n");
    inOrder(root);
    printf("\n----------------3.后序递归遍历-----------------\n");
    postOrderRecursion(root);
    printf("\n后序非递归遍历\n");
    postOrder(root);
    printf("\n----------------4.层次遍历---------------------\n");
    levelOrder(root);
    */
    
    return 0;
}